package com.squirrel.michale.search5;

import java.util.Arrays;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/18 12:15 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0034 {

public int[] searchRange(int[] numbers, int target) {

        int left = 0;
        int right = numbers.length - 1;

        int middle = 0;
        int firstTarget = -1;
        int startIndex = -1;
        int endIndex = -1;
        // 寻找target
        while (left <= right) {
            middle = left + ((right - left) >> 1);

            if (numbers[middle] == target) {
                firstTarget = middle;
                break;
            } else if (numbers[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }

        }


        if (firstTarget == -1) {
            return new int[]{-1, -1};
        } else {
            // 寻找左边界
            left = 0;
            right = middle;


            while (left <= right) {
                middle = left + ((right - left) >> 1);
                if (numbers[middle] == target) {
                    if (startIndex == -1) {
                        startIndex = middle;
                    } else {
                        startIndex = middle < startIndex ? middle : startIndex;
                    }
                    right = middle - 1;
                } else {
                    left = middle + 1;
//                    startIndex = left > startIndex ? left : startIndex;
                }
            }

            // 寻找右边界
            left = firstTarget;
            right = numbers.length -1;

            while (left <= right) {
                middle = left + ((right - left) >> 1);
                if (numbers[middle] == target) {
                    endIndex = left > endIndex ? left : endIndex;
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
            return new int[]{startIndex, endIndex};
        }
    }

    public int[] searchRange2(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        int middle = 0;
        int firstTarget = -1;

        // 寻找target
        while (left <= right) {
            middle = left + ((right - left) >> 1);
            if (nums[middle] == target) {
                firstTarget = middle;
                break;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }

        }


        if (firstTarget == -1) {
            return new int[]{-1, -1};
        } else {
            // 寻找左边界
            left = 0;
            right = middle;

            int startIndex = middle;
            int endIndex = middle;
            while (left <= right) {
                middle = left + ((right - left) >> 1);
                if (nums[middle] == target) {
                    startIndex = middle < startIndex ? middle : startIndex;
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }

            // 寻找右边界
            left = firstTarget;
            right = nums.length -1;

            while (left <= right) {
                middle = left + ((right - left) >> 1);
                if (nums[middle] == target) {
                    endIndex = middle > endIndex ? middle : endIndex;
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
            return new int[]{startIndex, endIndex};
        }
    }



    public int[] searchRange3 (int[] nums, int target) {
        int upper = upperBound(nums,target);
        int low = lowerBound(nums,target);
        //不存在情况
        if (upper < low) {
            return new int[]{-1,-1};
        }
        return new int[]{low,upper};
    }
    //计算下边界
    int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //这里需要注意，计算mid
            int mid = left + ((right - left) >> 1);
            if (target <= nums[mid]) {
                //当目标值小于等于nums[mid]时，继续在左区间检索，找到第一个数
                right = mid - 1;

            }else if (target > nums[mid]) {
                //目标值大于nums[mid]时，则在右区间继续检索，找到第一个等于目标值的数
                left = mid + 1;

            }
        }
        return left;
    }
    //计算上边界
    int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target >= nums[mid]) {
                left = mid + 1;
            }else if (target < nums[mid]) {
                right = mid - 1;
            }
        }
        return right;
    }

//    作者：袁记菜馆
//    链接：https://leetcode.cn/problems/search-insert-position/solutions/536357/yi-wen-dai-ni-gao-ding-er-fen-cha-zhao-j-69ao/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


    // [0,0,1,1,2,2,2,2,3,3,4,4,4,5,6,6,6,7,8,8] 4

    public static void main(String[] args) {
        int[] nums = new int[]{0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8};

        LeetCode0034 leetCode0034 = new LeetCode0034();
        System.out.println(Arrays.toString(leetCode0034.searchRange2(nums, 4)));

    }

     public static void main2(String[] args) {


        LeetCode0034 leetCode0034 = new LeetCode0034();
        leetCode0034.test1(leetCode0034);
        System.out.println("----------------------------------------------");
        leetCode0034.test2(leetCode0034);

    }

    private void test1(LeetCode0034 leetCode0034) {
        int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(leetCode0034.searchRange(nums, 8)));
        System.out.println(Arrays.toString(leetCode0034.searchRange(nums, 6)));

        int[] nums2 = new int[]{5, 7, 7, 8, 8, 8,8,8,8,8,8,9,10};
        System.out.println(Arrays.toString(leetCode0034.searchRange(nums2, 8)));
        System.out.println(Arrays.toString(leetCode0034.searchRange(nums2, 6)));


        int[] nums3 = new int[]{8, 8, 8, 8, 8, 8,8,8,8,8,8,9,10};
        System.out.println(Arrays.toString(leetCode0034.searchRange(nums3, 8)));


        int[] nums4 = new int[]{8, 8, 8, 8, 8, 8,8,8,8,8,8,8,8};
        System.out.println(Arrays.toString(leetCode0034.searchRange(nums4, 8)));
    }


    private void test2(LeetCode0034 leetCode0034) {
        int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(leetCode0034.searchRange2(nums, 8)));
        System.out.println(Arrays.toString(leetCode0034.searchRange2(nums, 6)));

        int[] nums2 = new int[]{5, 7, 7, 8, 8, 8,8,8,8,8,8,9,10};
        System.out.println(Arrays.toString(leetCode0034.searchRange2(nums2, 8)));
        System.out.println(Arrays.toString(leetCode0034.searchRange2(nums2, 6)));


        int[] nums3 = new int[]{8, 8, 8, 8, 8, 8,8,8,8,8,8,9,10};
        System.out.println(Arrays.toString(leetCode0034.searchRange2(nums3, 8)));


        int[] nums4 = new int[]{8, 8, 8, 8, 8, 8,8,8,8,8,8,8,8};
        System.out.println(Arrays.toString(leetCode0034.searchRange2(nums4, 8)));
    }
}
